package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.Arrays;

public class AVLTreeDomo {
	@Test
	public void test(){
		//左旋转测试数组
		//int[] arr = {4,3,6,5,7,8};
		//右旋转测试数组
		int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
		AVLTree avlTree = new AVLTree();
		Arrays.stream(arr).forEach((a) -> avlTree.add(new AVLTree.Node(a)));
		AVLTree.Node root = avlTree.getRoot();
		root.scortToAVL();
		System.out.println();
		System.out.println("树的总高度:" + root.getHeight());
		System.out.println("左子树高度:" + root.getLeftHeight());
		System.out.println("右子树高度:" + root.getRightHeight());
		System.out.println(root);
		//System.out.println(root.left.right.right);
		System.gc();
	}
}

/**
 * 平衡二叉树(AVL树)
 */
class AVLTree{
	Node root;
	//添加
	public void add(Node node){
		if (root == null){
			root = node;
		}else {
			root.add(node);
		}
	}
	
	//删除
	public void del(int value){
		if (root == null){
			return;
		}
		
		//查找目标节点
		Node targetNode = find(value);
		//判断targetNode是否为null,为null在数中没有此节点
		if (targetNode == null){
			return;
		}
		//判断此树是否只有一个节点
		if (root.left == null && root.right == null){
			root = null;
		}
		//查询它的父节点
		Node parent = findParent(value);
		//如果删除的节点有左右子树
		if (targetNode.left != null && targetNode.right != null){
			//首先要获取该节点右子树的最小节点
			Node node = targetNode.right;
			while(node.left != null){
				node = node.left;
			}
			/*
			 * 将找到的最小节点删除,这里是递归删除,因为在上面时按照node.left为null
			 * 的条件进行查找,所以在递归后一定是按照删除子节点或者删除一颗子树的节点
			 * 方式进行删除节点操作,不会进行无限递归
			 */
			del(node.value);
			//将找到的最小节点值赋值给需要删除的节点
			targetNode.value = node.value;
			return;
		}
		/*
		 * 删除子节点或者有一颗子树的节点
		 * 	在这里由于无论删除的是子节点还是有一颗子树的节点,最后的删除操作
		 *	都是类似于parent.left = targetNode.left这样的操作
		 *  如果targetNode没有一颗子树,那么就相当于parent.left = null
		 *  如果有子树,就把parent.left = targetNode.left就可以了
		 *  所以需要判断该节点的子树是左子树还是右子树
		 */
		Node tar = null;
		tar = targetNode.left != null ? targetNode.left : targetNode.right;
		/*
		 * 判断是左子节点还是右子节点,
		 * 	在这里需要判断parent.left不为null后才能验证parent.left.value跟value相同
		 * 	无论是删除的子节点还是有一颗子树的节点都需要判断
		 */
		if (parent != null) {
			if (parent.left != null && parent.left.value == value) {
				parent.left = tar;
			}
			if (parent.right != null && parent.right.value == value) {
				parent.right = tar;
			}
		} else {
			root = tar;
		}
	}
	
	//查找节点
	public Node find(int value){
		if (root == null){
			return null;
		} else {
			return root.find(value);
		}
	}
	
	//查找父节点
	public Node findParent(int value){
		if (root == null){
			return null;
		} else {
			return root.findParent(value);
		}
	}
	
	//中序遍历
	public void inFixOrder(){
		if (root != null){
			root.inFixOrder();
		}
	}
	
	public Node getRoot() {
		return root;
	}
	
	
	/**
	 * 二叉树的节点Node
	 * 原节点类中拥有的方法:
	 * 1.中序遍历(inFixOrder)
	 * 2.根据value查找Node(find)
	 * 3.根据value查找此节点的父节点parentNode(findParent)
	 * 4.添加(add)
	 * 要创建一个平衡二叉树,需要在此类中再创建几个方法
	 * 1.以调用节点为根节点获取树的高度(getHeight)
	 * 2.获取左子树的高度(getLeftHeight)
	 * 3.获取左子树的高度(getRightHeight)
	 */
	static class Node{
		int value;
		Node left;
		Node right;
		
		//构造器
		public Node(int value) {
			this.value = value;
		}
		
		//获取左子树的高度
		public int getLeftHeight(){
			if (left == null){
				return 0;
			}
			return left.getHeight();
		}
		
		//获取右子树的高度
		public int getRightHeight(){
			if (right == null){
				return 0;
			}
			return right.getHeight();
		}
		
		//以调用节点为根节点获取树的高度
		public int getHeight(){
			return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
		}
		
		//左旋转
		private void leftRotate(){
			//创建一个新的节点
			Node newNode = new Node(value);
			//将新节点的左子树设置为当前节点的左子树
			newNode.left = left;
			//将新节点的右子树设置为当前节点的右子树的左子树
			newNode.right = right.left;
			//将当前节点的值替换为右子节点的值
			value = right.value;
			//将当前节点的右子树设置为当前节点右子树的右子树
			right = right.right;
			//将新节点设置为当前节点的左子树
			left = newNode;
		}
		
		//右旋转
		public void rightRotate(){
			Node newNode = new Node(value);
			newNode.right = right;
			newNode.left = left.right;
			value = left.value;
			left = left.left;
			right = newNode;
		}
		
		//双旋转
		public void leftAndRightRotate(){
			//当添加完一个节点后,判断如果(右子树高度 - 左子树高度) > 1,发生左旋转
			if (getRightHeight() - getLeftHeight() > 1){
				//在这里需要判断如果右子树的左子树高度大于右子树的右子树高度,还要进行右旋转
				if (right != null && right.getLeftHeight() > right.getRightHeight()){
					//对左子树进行左旋转
					right.rightRotate();
				}
				leftRotate();
				return;
			}
			
			//当添加完一个节点后,判断如果(左子树高度 - 右子树高度) > 1,发生右旋转
			if (getLeftHeight() - getRightHeight() > 1){
				//在这里需要判断如果左子树的右子树高度大于左子树的左子树高度,还要进行右旋转
				if (left != null && left.getRightHeight() > left.getLeftHeight()){
					//对左子树进行左旋转
					left.leftRotate();
				}
				//对当前节点进行右旋转
				rightRotate();
			}
		}
		
		public void scortToAVL(){
			if (this.left != null){
				this.left.scortToAVL();
			}
			if (this.right != null){
				this.right.scortToAVL();
			}
			leftAndRightRotate();
			//System.out.print(this);
			
			
			
		}
		
		//查找节点
		public Node find(int value){
			if (value == this.value){
				return this;
			}
			
			if (value < this.value && this.left != null){
				return this.left.find(value);
			}else if (value >= this.value && this.right != null){
				return this.right.find(value);
			}else{
				return null;
			}
		}
		//查找节点的父节点
		public Node findParent(int value){
			if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)){
				return this;
			}
			
			if (this.value > value && this.left != null){
				return this.left.findParent(value);
			}else if(this.value <= value && this.right != null){
				return this.right.findParent(value);
			}else{
				return null;
			}
		}
		
		
		//添加方法
		public void add(Node node){
			if (node == null){
				return;
			}
			
			if (node.value < this.value){
				if (this.left == null){
					this.left = node;
				} else {
					this.left.add(node);
				}
			}else{
				if (this.right == null){
					this.right = node;
				} else {
					this.right.add(node);
				}
			}
			//调用双旋转,调整成平衡二叉树
			//leftAndRightRotate();
		}
		
		//中序遍历
		public void inFixOrder(){
			if (this.left != null){
				this.left.inFixOrder();
			}
			System.out.print(this);
			if (this.right != null){
				this.right.inFixOrder();
			}
		}
		
		@Override
		public String toString() {
			return value + " ";
		}
		
		@Override
		protected void finalize() throws Throwable {
			//System.out.println(value + "要死了!!");
		}
	}
}
